We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. We give the first algorithm for this setting that obtains a constant approximation factor on the optimal cost under a random arrival order, an exponential improvement over previous work. This is also the first constant approximation guarantee that holds without any structural assumptions on the input data. Moreover, the number of selected centers is only quasi-linear in k. Our algorithm and analysis are based on a careful cost estimation that avoids outliers, a new concept of a linear bin division, and a multiscale approach to center selection.

Clustering is a fundamental unsupervised learning task used for various applications, such as anomaly detection (Leung and Leckie, 2005), recommender systems (Shepitsen et al., 2008) and cancer diagnosis (Zheng et al., 2014). In recent years, research on sequential clustering has been actively studied, motivated by applications in which data arrives sequentially, such as online recommender systems (Nasraoui et al., 2007) and online community detection (Aggarwal, 2003). In this work, we study k-median clustering in the sequential no-substitution setting, a term first introduced in Hess and Sabato (2020). In this setting, a stream of data points is sequentially observed, and some of these points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. This setting is motivated by applications in which center selection is mapped to a real-world irreversible action, such as providing users with promotional gifts or recruiting participants to a clinical trial. The goal in the no-substitution k-median setting is to obtain a near-optimal k-median risk value, while selecting a number of centers that is as close as possible to k.